package algorithm.poj;

import java.util.LinkedList;
import java.util.Set;

public class Graph {

	/**
	 * DFS 深度遍历
	 * @param s
	 * @param N
	 * @param edges
	 */
	public static DFSResult DFS(int N, Set<Integer>[] edges) {
		
		char[] color = new char[N];
		int[] p = new int[N];
		int[] d = new int[N];
		int[] f = new int[N];
		for (int u = 0; u < N; u ++) {
			color[u] = 'w';
			p[u] = -1;
		}
		int time = 0;
		for (int i = 0; i < N; i ++) {
			if (color[i] == 'w') {	//start from u
				LinkedList<Integer> stack = new LinkedList<Integer>();
				stack.push(i);
				while (!stack.isEmpty()) {
					int u = stack.peek();
					if (color[u] == 'w') {
						color[u] = 'g';
						time ++;
						d[u] = time;
					}
					boolean find = false;
					for (int v: edges[u]) {
						if (color[v] == 'w') {
							stack.push(v);
							p[v] = u;
							find = true;
							break;
						}
					}
					if (!find) {
						u = stack.pop();
						color[u] = 'b';
						time ++;
						f[u] = time;
					}
				}
			}
		}
		
		//return 
		DFSResult r = new DFSResult();
		r.p = p;
		r.d = d;
		r.f = f;
		return r;
	}
	
	public static class DFSResult {
		int[] p;
		int[] d;
		int[] f;
	}

}
